package com.zang.greedy;

/**
 * @author ZVerify
 * @since 2022/11/23 18:35
 * @see <a href="https://leetcode.cn/problems/monotone-increasing-digits/">...</a>
 **/
public class 单调递增的数字 {
    // 局部最优推全局最优，我们要考虑当前变成的数字不能大于传递给我们的参数所以要从后往前遍历
    // 如果当前数字大于后边的数字说明这一段不是递增的所以要将当前数字减小一个(为了比传递进来的参数小)
    // 整体遍历一遍然后将我们最后一个进行更改的数字后面的数字都变成'9'，就是最大的了
    public int monotoneIncreasingDigits(int n) {
        String value = String.valueOf(n);
        char[] array = value.toCharArray();

        int start = array.length;
        for (int i = array.length-2; i >=0 ; i--) {
            if (array[i] > array[i+1]) {
                array[i]-=1;
                start = i+1;
            }
        }
        for (int i = start; i < array.length; i++) {
            array[i] = '9';
        }

        return Integer.parseInt(String.valueOf(array));

    }
}
